package 回溯法;

import java.util.Arrays;
import java.util.function.IntConsumer;

/**
 * Copyright (C) 2023 思创数码科技股份有限公司
 * <p/>
 * 版权所有
 * <p/>
 * 类名　　  : 最小分配任务数量
 * 功能概要  :
 *
 * @author yangwk
 * @date 2024/5/18 14:25
 */
public class 最小分配任务数量 {
    static int N = 8;
    static int minCost = Integer.MAX_VALUE;
    static int[] temp = new int[N];
    static int[][] c = new int[N][N];
    static int[] task = new int[N];
    static int[] worker = new int[N];

    static void plan(int k, int cost) {
        int i;
        if ((k >= N) && cost < minCost) {
            minCost = cost;
            for (i = 0; i < N; i++) temp[i] = task[i];
        } else {
            for (i = 0; i < N; i++)
                if (worker[i] == 0 && cost+c[k][i]<minCost) {
                    worker[i] = 1;
                    task[k] = i;
                    plan(k + 1, cost + c[k][i]);
                    task[k] = 0;
                    worker[i] = 0;
                }
        }
    }
    public static void main(String[] args) {
        c = new int[][]{{0, 1, 2, 3, 4, 5, 6, 7}, {0, 2, 2, 3, 4, 5, 6, 7}, {0, 1, 2, 4, 4, 5, 6, 7}, {0, 1, 5, 3, 4, 5, 6, 7}
                , {0, 1, 12, 3, 4, 12, 6, 7}, {0, 1, 2, 3, 4, 12, 6, 7}, {0, 1, 2, 3, 44, 5, 6, 7}, {0, 1, 2, 3, 4, 5, 6, 7}};
        plan(0, 0);
        Arrays.spliterator(temp).forEachRemaining((IntConsumer) value -> System.out.println(value));
    }
}
